import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Leetcode {
}

//leetcode:30:串联所有单词的字串
class Solution1 {
    public List<Integer> findSubstring(String s, String[] words) {
        //创建一个链表用于返回
        List<Integer> list = new ArrayList<>();
        //创建哈希表
        Map<String,Integer> hash1 = new HashMap<>();
        //将words数组的元素放入hash1中，如果存在直接让对应的数量加一，不存在从0开始加一
        for(String ss : words){
            hash1.put(ss,hash1.getOrDefault(ss,0)+1);
        }
        //得到每个字符串的长度
        int len = words[0].length();
        //得到words中字符串的个数
        int m = words.length;
        //每个单词的长度代表我们每次找时的初始位置
        for(int i = 0;i < len;i++){
            //创建哈希表
            Map<String,Integer> hash2 = new HashMap<>();
            for(int left = i,right = i,count = 0;right+len <= s.length();right+=len){
                //遍历数组，得到len长度的字符串
                String in = s.substring(right,right+len);
                //如果字符串宅hash2中存在直接让对应的数量加一，不存在从0开始加一
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                //如果hash2对应字符串的数量小于等于hash1对应字符串的数量，就让有效元素个数加一
                if(hash2.get(in) <= hash1.getOrDefault(in,0)){
                    count++;
                }
                //如果我们移动的位置超过了我们words数组所有“字符”的个数就要让left往右走
                if(right-left+1 > len*m){//个数乘于一个单词的长度就是字符的个数
                    String out = s.substring(left,left+len);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)){//如果我们要移除字符串的个数小于等于hash1字符串的个数就让有效长度减一
                        count--;
                    }
                    hash2.put(out,hash2.get(out)-1);//让要移除字符串的数量减一
                    left+=len;//让left移动一个单词的长度
                }
                //如果有效长度等于我们words中字符串的个数，就将此时left位置传入链表当中
                if(count == m) list.add(left);
            }
        }
        return list;
    }
}

//leetcode:76:最小覆盖字串
class Solution2 {
    public String minWindow(String ss, String tt) {
        //将字符串转变成字符数组
       char[] s = ss.toCharArray();
       char[] t = tt.toCharArray();
       //创建一个容量为128的的数组用来存储所有字符，模拟哈希表
       int[] hash1 = new int[128];
       //得到t数组中有效字符的个数
       int kinds = 0;
       for(char ch : t){
        if(hash1[ch]++ == 0){//数量等于0就是有效的元素
           kinds++;
        }
       }
       int min = Integer.MAX_VALUE,begin = -1;
       int[] hash2 = new int[128];
       for(int left = 0,rigth = 0,count = 0;rigth < s.length;rigth++){
        //遍历数组s，如果hash2对应元素的个数和hash1对应元素的个数相等，就让有效元素个数加一
        char in = s[rigth];
        if(++hash2[in] == hash1[in]){
            count++;
        }
        //如果有效元素个数相等
        while(count == kinds){
            //得到存在有效元素个数最小的字符串长度
            if(rigth-left+1 < min){
                begin = left;//让begin记录left的位置
                min = rigth-left+1;//得到新的最小长度
            }
            //移除左边的元素，让left往右走
            char out = s[left++];
            //如果hash2对应元素的个数和hash1对应元素的个数相等，就让有效元素个数和元素对应的数量减一
            if(hash2[out]-- == hash1[out]){
                count--;
            }
        }
       }
       //如果begin没有改变，就代表没有符合的字符串，返回空字符串，如果改变了，就返回ss字符串中begin到begin+min(最小长度)的字符串
       return begin == -1 ? new String() : ss.substring(begin,begin+min);
    }
}

